// 笔试强训2025/3/15
// 链表相加（二）

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param head1 ListNode类 
         * @param head2 ListNode类 
         * @return ListNode类
         */
        ListNode* addInList(ListNode* head1, ListNode* head2) {
            // write code here
            stack<int> st1, st2;
            ListNode *cur1 = head1, *cur2 = head2;
            while(cur1)
            {
                st1.emplace(cur1->val);
                cur1 = cur1->next;
            }
            while(cur2)
            {
                st2.emplace(cur2->val);
                cur2 = cur2->next;
            }
    
            ListNode* cur = nullptr;
            int carry = 0;
            while(!st1.empty() || !st2.empty() || carry)
            {
                if(!st1.empty()){
                    carry += st1.top();
                    st1.pop();
                }
                if(!st2.empty()){
                    carry += st2.top();
                    st2.pop();
                }
                ListNode* newnode = new ListNode(carry % 10);
                carry = carry / 10;
                newnode->next = cur;
                cur = newnode;
            }
            return cur;
        }
    };